Fundamental Lemma Of Sieve Theory
   HOME

TheInfoList



OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, the fundamental lemma of sieve theory is any of several results that systematize the process of applying sieve methods to particular problems. Halberstam & Richert write: Diamond & Halberstam attribute the terminology ''Fundamental Lemma'' to Jonas Kubilius.


Common notation

We use these notations: * A is a set of X positive integers, and A_d is its subset of integers divisible by d * w(d) and R_d are functions of A and of d that estimate the number of elements of A that are divisible by d, according to the formula : \left\vert A_d \right\vert = \frac X + R_d . :Thus w(d)/d represents an approximate density of members divisible by ''d'', and R_d represents an error or remainder term. * P is a set of primes, and P(z) is the product of those primes \leq z * S(A, P, z) is the number of elements of A not divisible by any prime in P that is \leq z * \kappa is a constant, called the sifting density, that appears in the assumptions below. It is a
weighted average The weighted arithmetic mean is similar to an ordinary arithmetic mean (the most common type of average), except that instead of each of the data points contributing equally to the final average, some data points contribute more than others. The ...
of the number of
residue class In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
es sieved out by each prime.


Fundamental lemma of the combinatorial sieve

This formulation is from Tenenbaum. Other formulations are in Halberstam & Richert, in Greaves, and in Friedlander & Iwaniec. We make the assumptions: * w(d) is a
multiplicative function In number theory, a multiplicative function is an arithmetic function ''f''(''n'') of a positive integer ''n'' with the property that ''f''(1) = 1 and f(ab) = f(a)f(b) whenever ''a'' and ''b'' are coprime. An arithmetic function ''f''(''n'') i ...
. * The sifting density \kappa satisfies, for some constant C and any real numbers \eta and \xi with 2\leq \eta\leq \xi: :\prod_ \left( 1 - \frac \right) ^ < \left( \frac \right) ^\kappa \left( 1 + \frac \right). There is a parameter u\geq 1 that is at our disposal. We have uniformly in A, ''X'', ''z'', and u that :S(a,P,z) = X \prod_ \left( 1 - \frac \right) \ + O\left(\sum_ , R_d, \right). In applications we pick ''u'' to get the best error term. In the sieve it is related to the number of levels of the
inclusion–exclusion principle In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as : , A \cu ...
.


Fundamental lemma of the Selberg sieve

This formulation is from Halberstam & Richert. Another formulation is in Diamond & Halberstam. We make the assumptions: * w(d) is a
multiplicative function In number theory, a multiplicative function is an arithmetic function ''f''(''n'') of a positive integer ''n'' with the property that ''f''(1) = 1 and f(ab) = f(a)f(b) whenever ''a'' and ''b'' are coprime. An arithmetic function ''f''(''n'') i ...
. * The sifting density \kappa satisfies, for some constant C and any real numbers \eta and \xi with 2\leq \eta\leq \xi: \qquad \sum_ \frac < \kappa \ln \frac + C. * ''\frac < 1-c'' for some small fixed ''c'' and all ''p''. * '', R(d), \leq w(d)'' for all squarefree ''d'' whose prime factors are in ''P''. The fundamental lemma has almost the same form as for the combinatorial sieve. Write ''u = \ln /\ln''. The conclusion is: :S(a,P,z) = X \prod_ \left( 1 - \frac \right) \. Note that ''u'' is no longer an independent parameter at our disposal, but is controlled by the choice of ''z''. Note that the error term here is weaker than for the fundamental lemma of the combinatorial sieve. Halberstam & Richert remark: "Thus it is not true to say, as has been asserted from time to time in the literature, that Selberg's sieve is always better than Brun's."


Notes

{{Reflist Sieve theory Theorems in analytic number theory